class Sort {

  constructor( unsorted, isReverse ){
  
    this.unsorted = unsorted;
    this.isReverse = isReverse;
    
    if( unsorted ) {
      this.origin = [...unsorted];
    }
    
    this.init();
  }

  init() {
    this.resetCount();
  }

  set(unsorted) {
    this.unsorted = unsorted;
    this.init();
  }

  resetCount() {
    this.runCount = 0;
    this.swapCount = 0;
    this.stepCount = 0;
    this.loopCount = 0;
  }

  size(){
    return this.unsorted.length;
  }

  /**
   * 生成随机数组
   * @param {*} size 
   * @param {*} mode 数据模式
   * 0 顺序[1:size]
   * 1 逆序[size:1]
   * 2 范围在[1:size]的无重复随机序列
   * 3 范围在[1:size]的可重复随机序列
   */
  randomData( size, mode=0 ) {

    var unsorted = [];
    const sorted = [];
    
    for( var i = 1; i <= size; i++ ) {
      sorted.push(i);
    }

    switch(mode){
      case 0:
        unsorted = sorted;
        break;
      case 1:
        unsorted = sorted.reverse()
        break;
      case 2:
        while(sorted.length>0) {
          unsorted.push(parseInt( sorted.splice(Math.floor(Math.random()*sorted.length), 1)));
        }
        break;
      case 3:
        for( let i = 1; i <= size; i++ ) {
          unsorted.push( Math.floor( Math.random() * size ) + 1 );
        }
        break;
      default:
        unsorted = sorted;
        break;
    }

    this.unsorted = unsorted;
    this.origin = [...unsorted];

    this.init();
  }

  /**
   * 检测列表是否有序
   * @param {*} arr 
   * @returns -1 错误 0 无序 1 顺序 2 逆序 3 等值
   */
  check() {

    const arr = this.unsorted;
  
    if( !arr || arr.length < 2 ) return -1;

    let j = 0;
    for( ; j < arr.length - 1; j++ ){
      if( arr[j] !== arr[ j + 1] ) break;
    }

    if( j === arr.length - 1 ) {
      return 3;
    }

    var isReverse = arr[j] > arr[j + 1];
    
    for( var i = 2, il = arr.length; i < il; i++ ) {
      if( isReverse && arr[i] > arr[i - 1] ) {
        return 0;
      }
      else if( !isReverse && arr[i] < arr[i-1] ){
        return 0;
      }
    }

    if( isReverse ) {
      return 2;
    }
    else {
      return 1;
    }

  }

  reset() {
    this.resetCount();
    this.unsorted = [...this.origin];
  }

  swap( ia, ib ) {
    const unsorted = this.unsorted;

    const tmp = unsorted[ia];
    unsorted[ia] = unsorted[ib];
    unsorted[ib] = tmp;

    this.swapCount++;

  }

  doOneStep() {
    return true;
  }

  doOneLoop() {
    return true;
  }

  run() {

  }
}

class BubbleSort extends Sort{
  
  doOneStep() {

    const unsorted = this.unsorted;
    const len = this.unsorted.length;
    const isReverse = this.isReverse;
    
    var i = this.loopCount;
    var j = this.stepCount;

    if( i >= len ) return true;  // 已结束

    if( j >= (len - i) - 1 ) {
      i++;
      j = 0;
    }

    if( i >= len ) return true;

    if( isReverse ) {
      if( unsorted[j] < unsorted[j+1] ){
        this.swap(j, j + 1);
      }
    }
    else {
      if( unsorted[j] > unsorted[j+1] ){
        this.swap(j, j + 1);
      }
    }

    j++;

    if( j >= (len - i) - 1 ) {
      i++;
      j = 0;
    }

    this.stepCount = j;
    this.loopCount = i;

    return false;

  }

  doOneLoop() {
    const unsorted = this.unsorted;
    const len = this.unsorted.length;
    const isReverse = this.isReverse;
    var i = this.loopCount;

    if( i >= len ) {
      return true;
    }

    for( let j = 0, jl = len - i - 1; j < jl; j++ ) {
      if( isReverse ) {
        if( unsorted[j] < unsorted[j+1] ){
          this.swap(j, j + 1);
        }
      }
      else {
        if( unsorted[j] > unsorted[j+1] ){
          this.swap(j, j + 1);
        }
      }
    }

    this.loopCount = i + 1;
    this.stepCount = 0;

    return false;

  }

  run() {

    const unsorted = this.unsorted;
    const isReverse = this.isReverse;
    this.resetCount();
    
    for( let i = 0, il = unsorted.length; i < il; i++ ) {
      for( let j = 0, jl = il - i - 1; j < jl; j++ ) {
        if( isReverse ) {
          if( unsorted[j] < unsorted[j+1] ){
            this.swap(j, j + 1);
          }
        }
        else {
          if( unsorted[j] > unsorted[j+1] ){
            this.swap(j, j + 1);
          }
        }

        this.runCount++;
      }
    }
  }

}

class InsertSort extends Sort {

  doOneStep() {

    const unsorted = this.unsorted;
    const len = this.unsorted.length;
    const isReverse = this.isReverse;
    
    var i = this.loopCount;
    var j = this.stepCount;

    if( i >= len ) return true;  // 已结束

    if( j <= 0 ) {
      i++;
      j = i;
    }

    if( i >= len ) return true;

    if( isReverse ) {
      if( unsorted[j] > unsorted[j-1] ){
        this.swap(j, j-1);
        j--;
      }
      else{
        i++;
        j=i;
      }
    }
    else {
      if( unsorted[j] < unsorted[j-1] ){
        this.swap(j, j-1);
        j--;
      }
      else{
        i++;
        j=i;
      }
    }

    this.stepCount = j;
    this.loopCount = i;

    return false;

  }

  doOneLoop() {
    const unsorted = this.unsorted;
    const len = this.unsorted.length;
    const isReverse = this.isReverse;
    var i = this.loopCount;

    if( i >= len ) {
      return true;
    }

    for( let j = i; j > 0; j-- ) {
      if( isReverse ) {
        if( unsorted[j] <= unsorted[j-1] ){
          break;
        }
      }
      else {
        if( unsorted[j] >= unsorted[j-1] ){
          break;
        }
      }
      this.swap(j, j-1);
    }

    this.loopCount = i + 1;
    this.stepCount = i;

    return false;

  }
  
  run() {

    const unsorted = this.unsorted;
    const isReverse = this.isReverse;
    this.resetCount();
    
    for( let i = 1, il = unsorted.length; i < il; i++ ) {
 
      for( let j = i; j > 0; j-- ) {
        if( isReverse ) {
          if( unsorted[j] <= unsorted[j-1] ){
            break;
          }
        }
        else {
          if( unsorted[j] >= unsorted[j-1] ){
            break;
          }
        }
        this.swap(j, j-1);
      }
    }
  }
}

class SelectSort extends Sort {

  minIndex = 0;

  doOneStep() {

    const unsorted = this.unsorted;
    const len = this.unsorted.length;
    const isReverse = this.isReverse;
    
    var i = this.loopCount;
    var j = this.stepCount;

    if( i >= len ) return true;  // 已结束

    if( j >= len ) {
      if( this.minIndex !== i ) {
        this.swap( this.minIndex, i );
      }
      i++;
      j = i;
      this.minIndex = i;
    }

    if( i >= len ) return true;

    if( isReverse ) {
      if( unsorted[j] > unsorted[ this.minIndex ] ){
        this.minIndex = j;
      }
    }
    else {
      if( unsorted[j] < unsorted[ this.minIndex ] ){
        this.minIndex = j;
      }
    }

    this.stepCount = j + 1;
    this.loopCount = i;

    return false;

  }

  doOneLoop() {
    const unsorted = this.unsorted;
    const len = this.unsorted.length;
    const isReverse = this.isReverse;
    var i = this.loopCount;

    if( i >= len ) {
      return true;
    }

    var minIndex = i;

    for( let j = i + 1, jl = unsorted.length; j < jl; j++ ) {
      if( isReverse ) {
        if( unsorted[j] > unsorted[minIndex] ){
          minIndex = j;
        }
      }
      else {
        if( unsorted[j] < unsorted[minIndex] ){
          minIndex = j;
        }
      }
    }

    if( minIndex !== i ) {
      this.swap( minIndex, i );
    }

    this.loopCount = i + 1;
    this.stepCount = i;

    return false;

  }

  run() {

    const unsorted = this.unsorted;
    const isReverse = this.isReverse;
    this.resetCount();
    
    var minIndex = 0;
    for( let i = 0, il = unsorted.length; i < il; i++ ) {
      minIndex = i;

      for( let j = i + 1, jl = unsorted.length; j < jl; j++ ) {
        if( isReverse ) {
          if( unsorted[j] > unsorted[minIndex] ){
            minIndex = j;
          }
        }
        else {
          if( unsorted[j] < unsorted[minIndex] ){
            minIndex = j;
          }
        }
      }

      if( minIndex !== i ) {
        this.swap( minIndex, i );
      }

    }
  }
}

class ShellSort extends Sort {

  resetCount() {
    super.resetCount();

    this.loopCount = Math.floor( this.unsorted.length / 2 );
  }

  doOneStep() {

    const unsorted = this.unsorted;
    const len = this.unsorted.length;
    const isReverse = this.isReverse;
    
    var gap = this.loopCount;
    var i = this.stepCount;

    if( gap <= 0 ) return true;  // 已结束

    if( i >= len ) {
      gap = Math.floor(gap/2);
      i = gap;
    }

    if( gap <= 0 ) return true;

    var pre = i - gap;

    while (pre >= 0) {
      if( isReverse ) {
        if( unsorted[pre] < unsorted[pre+gap] ){
          this.swap( pre, pre+gap );
        }
      }
      else{
        if( unsorted[pre] > unsorted[pre+gap] ){
          this.swap( pre, pre+gap );
        }
      }
      pre -= gap;
    }    

    this.stepCount = i+1;
    this.loopCount = gap;

    return false;

  }

  doOneLoop() {
    const unsorted = this.unsorted;
    // const len = this.unsorted.length;
    const isReverse = this.isReverse;
    var gap = this.loopCount;

    if( gap <= 0 ) {
      return true;
    }

    for( var i = gap, il = unsorted.length; i < il; i++ ) {
      var pre = i - gap;

      while (pre >= 0) {
        if( isReverse ) {
          if( unsorted[pre] < unsorted[pre+gap] ){
            this.swap( pre, pre+gap );
          }
        }
        else{
          if( unsorted[pre] > unsorted[pre+gap] ){
            this.swap( pre, pre+gap );
          }
        }
        pre -= gap;
      }
      
    }

    this.loopCount = Math.floor( gap / 2 );
    this.stepCount = gap;

    return false;

  }

  run() {

    const unsorted = this.unsorted;
    const isReverse = this.isReverse;
    this.resetCount();
    
    var gap = Math.floor( unsorted.length / 2);

    while( gap > 0 ) {
      
      for( var i = gap, il = unsorted.length; i < il; i++ ) {
        var pre = i - gap;
  
        while (pre >= 0) {
          if( isReverse ) {
            if( unsorted[pre] < unsorted[pre+gap] ){
              this.swap( pre, pre+gap );
            }
          }
          else{
            if( unsorted[pre] > unsorted[pre+gap] ){
              this.swap( pre, pre+gap );
            }
          }
          pre -= gap;
        }
        
      }
      gap = Math.floor(gap / 2);
    }
  }
}

class MergeSort extends Sort {

  resetCount() {
    super.resetCount();

    this.tree = null;
  }

  doOneLoop() {
    const unsorted = this.unsorted;

    if( !this.tree ) {
      this.tree = {};
      this.maxDepth = -1;
      this.mergeSort(unsorted, this.tree);
      this.loopCount = this.maxDepth - 1;
    }

    if(this.loopCount < 0) return true;

    const tmp = [];
    this.depthSearch( this.tree, tmp, this.loopCount );
    for(var i = 0, il = unsorted.length; i < il; i++ ) {
      unsorted[i] = tmp[i];
    }

    this.loopCount--;
    return false;

  }

  depthSearch( root, arr , d ) {

    if ( !root ) return;

    if( root.depth === d ) {
      arr.push(...root.result);
    }
    else{
      if( root.left || root.right ) {
        this.depthSearch( root.left, arr, d );
        this.depthSearch( root.right, arr, d );
      }
      else{
        arr.push(...root.result);
      }
    }
  }

  run() {

    const unsorted = this.unsorted;
    this.resetCount();
    this.tree = {};
    this.maxDepth = -1;
    
    const tmp = this.mergeSort(unsorted, this.tree);

    for(var i = 0, il = unsorted.length; i < il; i++ ) {
      unsorted[i] = tmp[i];
    }

    // console.log( this.tree );

  }

  mergeSort( arr, node, depth=0 ) {
    node = node || {};

    node['data'] = [...arr];
    node['depth'] = depth;
    node['left'] = {};
    node['right'] = {};

    this.maxDepth = Math.max( this.maxDepth, depth );

    if( arr.length < 2 ){
      node['result'] = [...arr];
      return arr;
    }

    const middle = Math.floor( arr.length / 2 );

    const result = this.merge(
      this.mergeSort(arr.slice(0, middle), node.left, depth+1), 
      this.mergeSort(arr.slice(middle), node.right, depth+1)
    );

    node['result'] = [...result];

    return result;
  }

  merge( left, right ) {

    let result = [];
    const isReverse = this.isReverse;

    while ( left && left.length > 0 && right && right.length > 0) {

      if( isReverse ){
        result.push( left[0] > right[0] ? left.shift():right.shift() );
      }
      else{
        result.push( left[0] < right[0] ? left.shift():right.shift() );
      }
    }

    if( left && left.length > 0 ) {
      result.push(...left);
    }

    if( right && right.length > 0 ) {
      result.push(...right);
    }
   
    return result;
  }
  
}

class QuickSort extends Sort {
  
  resetCount() {
    super.resetCount();

    this.results = undefined;
  }

  doOneStep() {
    const unsorted = this.unsorted;
    this.stepCount = this.partition(unsorted, 0, unsorted.length-1);
  }

  doOneLoop() {
    const unsorted = this.unsorted;

    if( !this.results ) {
      this.results = [];
      this.quickSort(unsorted);
      this.loopCount = 0;
    }

    if(this.loopCount >= this.results.length) return true;

    for(var i = 0, il = unsorted.length; i < il; i++ ) {
      unsorted[i] = this.results[this.loopCount].result[i];
    }

    this.stepCount = this.results[this.loopCount].index;
    this.loopCount++;
  
    return false;

  }

  run() {

    const unsorted = this.unsorted;
    this.resetCount();
    this.results=[];
    
    this.quickSort(unsorted);

    // console.log(this.results);
  }

  quickSort( arr, left, right ) {
    left = left === undefined ? 0 : left;
    right = right === undefined ? arr.length - 1 : right;

    if( left < right ) {
      const partition_index = this.partition(arr, left, right);
      
      this.results.push({
        index: partition_index,
        result:[...arr],
      });

      this.quickSort(arr, left, partition_index - 1);
      this.quickSort(arr, partition_index + 1, right);
    }

    return arr;
  }

  partition(arr, left, right){
    const pivot = arr[left];
    const isReverse = this.isReverse;
    var i = left;
    var j = right;
    while (i < j){
      if(isReverse) {
        while (i < j && arr[j] <= pivot){
          j -= 1
        }
        arr[i] = arr[j]
        while (i < j && arr[i] > pivot){
            i += 1
        }
      }
      else{
        while (i < j && arr[j] > pivot){
            j -= 1
        }
        arr[i] = arr[j]
        while (i < j && arr[i] <= pivot){
            i += 1
        }
      }
      arr[j] = arr[i];
    }
    arr[i] = pivot;
    return i;
  }
}

class HeapSort extends Sort {

  resetCount(){
    super.resetCount();

    this.loopCount = -1;
  }

  doOneLoop(){
    const unsorted = this.unsorted;
    var len = unsorted.length - 1;

    if(this.loopCount < 0){
      this.buildMaxHeap();
      this.loopCount = len;
    }

    if( this.loopCount <= 0 ) return true;

    this.swap(0, this.loopCount);
    this.heapify(0, this.loopCount);

    this.loopCount--;
  }


  run(){
    const unsorted = this.unsorted;
    var len = unsorted.length - 1;
    this.buildMaxHeap();

    for( var i = unsorted.length - 1; i > 0; i-- ){
      this.swap(0, i);
      this.heapify(0, len--);
    }

  }

  buildMaxHeap(){
    const arr = this.unsorted;
    const middle = Math.floor(arr.length / 2);
    // 从堆最后一个可能有孩子的根开始调整
    for( var i = middle; i >= 0; i-- ){
      this.heapify( i, arr.length );
    }
  }

  heapify(i, unsorted_len){
    const arr = this.unsorted;
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    let largest = i;

    if (left < unsorted_len && arr[left] > arr[largest]) {
      largest = left;
    }
        
    if (right < unsorted_len && arr[right] > arr[largest]){
      largest = right;
    }

    // 递归调整堆
    if (largest !== i){
      this.swap( largest, i );
      this.heapify(largest, unsorted_len);
    }
  }
}

export default Sort;

export {
  BubbleSort,
  InsertSort,
  SelectSort,
  ShellSort,
  MergeSort,
  QuickSort,
  HeapSort,
}